1. Field
The present invention relates to a packet transmission method and device, an in particular to a packet transmission (transfer) method and device for reading a packet such as an Ethernet (trademark) frame from a packet buffer having temporarily stored the packet for each destination in a scheduling control in the field of art providing a function such as QoS (Quality of Service) control, priority control, bandwidth control, etc. in an layer 2 (L2) switch device used in an IP network.
2. Description of the Related Art
In a prior art device for switching a packet between networks or within a network, a scheduler (scheduling portion), an input FIFO and output FIFO have been employed to achieve a QoS control, priority control, or bandwidth control etc. This will be described referring to FIGS. 20-41 as follows:
Overall Arrangement of Packet Transmission Device: FIG. 20
As shown in FIG. 20, a packet transmission device 1 is generally composed of LIU (Line Interface Unit) cards 2#1-2#4 . . . (hereinafter, represented by reference numeral 2) and a switch (SW) card 3.
In this arrangement, packets coming from a network NW1 are received at physical ports P#0-P#n (hereinafter, a represented by a reference character P) of e.g. the LIU cards 2#1, 2#2 as shown by dotted routes R1, R2, and multiplexed respectively within the LIU cards 2#1, 2#2 to be provided to the switch card 3.
The switch card 3 identifies or discriminates the destination (output physical port) of each packet, and multiplies the packets and outputs them to e.g. the LIU card 2#3 where the corresponding physical port P exists. The LIU card 2#3 having received the packets from the switch card 3 performs a scheduling control and an output control, and outputs the packets to the network NW2 from the physical port P.
Conventional Arrangement of LIU Card: FIGS. 21-23
A conventional arrangement of the LIU card 2 is shown in FIG. 21 in which each block shown has the following functions:    (a) Write controller 11: Notifying, upon receiving a packet, received packet information (destination physical port number, packet length, etc.) to an address manager 14, and performing a write control of the packet in an address of a packet buffer 12 indicated by a free or vacant address from the address manager 14;    (b) Packet buffer 12: Storing an actual packet and outputting the packet in accordance with the scheduling control;    (c) Read controller 13: Performing, upon transmitting a packet, a read control of a packet from an address of the packet buffer 12 indicated by a read address from the address manager 14;    (d) Address manager 14: Controlling the following memories 141-144 with an address controller 140 to issue a write address and a read address:            Free address managing memory 141: Storing an available address;        Address chain managing memory 142: Managing connection of the order of packets stored in the packet buffer 12 and connection of data within the packets for each destination in the form of chain of address values (hereinafter, occasionally simplified as address);        Head address managing memory 143: Storing an address value in which a head packet for each destination physical port exists;        Tail address managing memory 144: Storing an address value in which a tail (final) packet for each destination physical port exists;            (e) Scheduler 15: Performing a scheduling control for selecting a destination (physical port) to be read by e.g. a round robin method while performing a bandwidth control by monitoring a contract bandwidth of a customer;    (f) Packet controller 16: Comprising the following three portions:            Destination discriminator 161: Discriminating or identifying a destination physical port number, determining which of packet FIFOs 162 should be used for the storage for each destination, and performing a write control;        Packet FIFO 162: Storing actual packets for each of the physical ports P#0-P#n;        Arbiter 163: Selecting the packet FIFO 162 to be read, performing a read control, and stopping reading packets for each physical port with a back pressure signal BP;            (g) Output portion 17: Comprising a demultiplexing (Dmux) portion 17 and “n” number of physical ports (P#0-P#n) 172, in which the Dmux portion 171 performs arranging transmission packets and generating the back pressure signal BP.
FIG. 22A shows a composition or format of the packet buffer 12, FIGS. 22B-22E show compositions of the memories 141-144, and FIG. 22F shows a composition of the packet FIFO 162, where the memories 143 and 144 store an address value for each physical port, and the packet FIFO 162 stores a packet for each physical port. The packet FIFO 162 shown has a memory composition for a single physical port.
Also, FIG. 23 shows a general composition of a packet.
Packet Receiving Operation: FIGS. 24 and 25
An operation of the LIU card 2 shown in FIG. 21 at the time of packet reception will now be described along flows indicated by reference numerals (1)-(4) shown in FIGS. 24 and 25, where in this receiving operation, only a read address counter value RAC of the memory 141 is incremented by only one address for one packet input but a write address counter value WAC does not run:
First, an operation (i) at the time of receiving the first packet for a certain destination will be described referring to FIG. 24 as follows:    (1) At the time of receiving a packet, the write controller 11 notifies received packet information (destination physical port number, packet length, etc.) to the address controller 140, which acquires a free address from the address managing memory 141;    (2) The address controller 140 writes a free address value acquired in the above (1) in an address of the corresponding physical port number (P#0-P#n) in the head address managing memory 143 (update of the head address value), and also writes a free address value in an address of the corresponding physical port number in the tail address managing memory 144 as well (update of the tail address value);    (3) The address controller 140 notifies received packet information for read controls to the scheduler 15;    (4) Address controller 140 outputs the free address value acquired in the above (1) to the write controller 11, which stores the received packet in an address of the packet buffer 12 indicated by the free address value.
Next, an operation (ii) at the time of receiving a packet toward a physical port having the same destination will be described along flows indicated by reference numerals (1)-(5) referring to FIG. 25 as follows:    (1) At the time of receiving a packet, the write controller 11 notifies received packet information (destination physical port number, packet length, etc.) to the address controller 140, which acquires a free address value from the free address managing memory 141;    (2) The address controller 140 writes the free address value acquired in the above (1) in an address of the corresponding physical port number in the tail address managing memory 144 (update of tail address value);    (3) The address controller 140 reads the head address value of the corresponding physical port number from the head address managing memory 143, and writes the free address value acquired in the above (1) in an address area indicated by the head address value in the address chain managing memory 142 (chaining operation of address value);    (4) The address controller 140 notifies the received packet information for read controls to the scheduler 15;    (5) The address controller 140 outputs the free address value acquired in the above (1) to the write controller 11, which stores the received packet in an address of the packet buffer 12 indicated by the free address value.Transition of Memory Contents: FIGS. 26A-26E to 33A-33E
The above receiving operations will now be described more specifically referring to FIGS. 26-33 showing contents of the memories 141-144 as follows:    1) Default state (before packet input): FIGS. 26A-26E
The memory contents at this initial setting are as follows:                Packet buffer 12: All addresses=free;        Free address managing memory 141: All addresses=available;        Address chain managing memory 142:                    All addresses=no chained next address;                        Head address managing memory 143:                    All addresses=no head address;                        Tail address managing memory 144:                    All addresses=no tail address.                            2) Input of packets A1, B1, C1: FIGS. 27A-27E
When having sequentially received three packets A1, B1, C1 respectively of destinations (physical ports) A, B, C, the memory contents are as follows:                Packet buffer 12:                    Packets A1, B1, C1 are respectively stored in addresses 0, 1, 2;                        Free address managing memory 141:                    Data of addresses 0, 1, 2 are unavailable;                        Address chain managing memory 142: Unchanged;        Head address managing memory 143:                    Head address of destination A=0,            Head address of destination B=1,            Head address of destination C=2;                        Tail address managing memory 144:                    Tail address of destination A=0,            Tail address of destination B=1,            Tail address of destination C=2.                            3) Input of packet A2: FIGS. 28A-28E
When having received the second packet A2 having the destination A, the memory contents are as follows:                Packet buffer 12: Packet is stored in address 3;        Free address managing memory 141:                    Data of address 3 is unavailable;                        Managing memory 142:                    Chained next address of address 0=3;                        Head address managing memory 143: Unchanged;        Tail address managing memory 144:                    Tail address of destination A=0→3 (changed from 0 to 3).                            4) Input of packet C: FIGS. 29A-29E
When having received the second packet C2 of the destination C, the memory contents are as follows:                Packet buffer 12: Packet is stored in address 4;        Free address managing memory 141:                    Data of address 4 is unavailable;                        Address chain managing memory 142:                    Chained next address of address 2=4;                        Head address managing memory 143: Unchanged;        Tail address managing memory 144:                    Tail address of destination C=2→4                            5) Input of packet A3: FIGS. 30A-30E
When having received the third packet A3 of the destination A, the memory contents are as follows:                Packet buffer 12: Packet is stored in address 5;        Free address managing memory 141:                    Data of address 5 is unavailable;                        Address chain managing memory 142:                    Chained next address of address 3=5;                        Head address managing memory 143: Unchanged;        Tail address managing memory 144:                    Tail address of destination A=3→5.                            6) Input of packet B2: FIGS. 31A-31E
When having received the second packet B2 of the destination B, the memory contents are as follows:                Packet buffer 12: Packet is stored in address 6;        Free address managing memory 141:                    Data of address 6 is unavailable;                        Address chain managing memory 142:                    Chained next address of address 1=6;                        Head address managing memory 143: Unchanged;        Tail address managing memory 144:                    Tail address of destination B=1→6.                            7) Input of packet C3: FIGS. 32A-32E
When having received the third packet C3 of the destination C, the memory contents are as follows:                Packet buffer 12: Packet is stored in address 7;        Free address managing memory 141:                    Data of address 7 is unavailable;                        Address chain managing memory 142:                    Chained next address of address 4=7;                        Head address managing memory 143: Unchanged;        Tail address managing memory 144:                    Tail address of destination C=4→7.                            8) Input of packet B3: FIGS. 33A-33E
When having received the third packet B3 of the destination B, the memory contents are as follows:                Packet buffer 12: Packet is stored in address 8;        Free address managing memory 141:                    Data of address 8 is unavailable;                        Address chain managing memory 142:                    Chained next address of address 6=8;                        Head address managing memory 143: Unchanged;        Tail address managing memory 144:                    Tail address of destination B=6→8.Packet Transmitting Operation: FIGS. 34 and 35A, 35B                        
Next, an operation of the LIU card 2 shown in FIG. 21 at the time of transmitting packets will be described along flows indicated by reference numeral (1)-(5) referring to FIGS. 34 and 35, where the read address counter value RAC of the memory 141 does not run but only the write address counter value WAC is incremented by one every time one packet is outputted:    (1) The address controller 140 having received a read physical port number determined by the scheduling control in the scheduler 15 reads a destination corresponding to the physical port number from the head address managing memory 143;    (2) The address controller 140 reads a chained next address value from the address chain managing memory 142 with the head address value acquired in the above (1), and writes the chained next address value in the address of the corresponding physical port number in the head address managing memory 143 (update of head address value);    (3) The address controller 140 returns the head address value acquired in the above (1) to the free address managing memory 141;    (4) The read controller 13 reads a packet from the packet buffer 12 with the head address value acquired in the above (1), and a destination discriminator 161 of the packet controller 16 discriminates the destination physical port number to be accumulated in the packet FIFO 162 of the corresponding physical port;    (5) The packets accumulated in the packet FIFO 162 are read therefrom at a read request from the arbiter 163 (e.g. a simple round robin operation) and outputted from the corresponding physical port 172 through the Dmux portion 171 of the output portion 17, where the Dmux portion 171 performs an output control in accordance with the actual rate, in which the outputting is stopped at the occurrence of a state exceeding the actual rate due to a burst or the like and the back pressure signal BP is transmitted to the arbiter 163, which controls the destination discriminator 161 to stop packet reading from the packet FIFO 162 of the corresponding physical port.
Specifically describing the above referring to FIGS. 35A and 35B, under contract of 1 Gbps on a physical basis for the output port, packets read from the packet buffer 12 beyond 1 Gbps in a burst mode can not be outputted, so that the back pressure signal BP is outputted from the Dmux portion 171 to the packet controller 16 to stop the packet outputting. When the packet outputting is stopped, the packets read from the packet buffer are accumulated in the packet FIFO 162 up to a level where any further packets can not be accumulated, at which the back pressure signal BP is outputted from the destination discriminator 161 of the packet controller 16 to the scheduler 15 to stop reading the packets from the packet buffer 12.
This keeps the rate of 1 Gbps in average as shown in FIG. 35B. It is to be noted that the issuance of read addresses to the packet buffer 12 is performed while the scheduler 15 is monitoring the contract bandwidth of the customer, as shown in FIG. 35A.
Transition of Memory Contents: FIGS. 36A-36E to 41A-41E
The above transmitting operation will be now described more specifically referring to FIGS. 36-41 showing contents of the memories 141-144, where the memory contents at the start of transmission are supposed to have the contents shown in FIG. 33:    1) Output of packet A1: FIGS. 36A-36E
When outputting the first packet A1 of the destination A based on the instructions of the scheduler 15, the memory contents are as follows:                Packet buffer 12: Address 0=free;        Free address managing memory 141:                    Data of address 0 is available;                        Address chain managing memory 142: Unchanged;        Head address managing memory 143:                    Head address of destination A=0→3;                        Tail address managing memory 144: Unchanged.            2) Output of packet A2: FIGS. 37A-37E
When outputting the second packet A2 of the destination A, the memory contents are as follows:                Packet buffer 12: Address 3=free;        Free address managing memory 141:                    Data of address 3 is available;                        Address chain managing memory 142: Unchanged;        Head address managing memory 143:                    Head address of destination A=3→5;                        Tail address managing memory 144: Unchanged.            2) Output of packet B1: FIGS. 38A-38E
When outputting the first packet B1 of the destination B, the memory contents are as follows:                Packet buffer 12: Address 1=free;        Free address managing memory 141:                    Data of address 1 is available;                        Address chain managing memory 142: Unchanged;        Head address managing memory 143:                    Head address of destination B=1→6;                        Tail address managing memory 144: Unchanged.            4) Output of packet B2: FIGS. 39A-39E
When outputting the second packet B2 of the destination B, the memory contents are as follows:                Packet buffer 12: Address 6=free;        Free address managing memory 141:                    Data of address 6 is available;                        Address chain managing memory 142: Unchanged;        Head address managing memory 143:                    Head address of destination B=6→8;                        Tail address managing memory 144: Unchanged.            5) Output of packet C1: FIGS. 40A-40E
When outputting the first packet C1 of the destination C, memory contents are as follows:                Packet buffer 12: Address 2=free;        Free address managing memory 141:                    Data of address 2 is available;                        Address chain managing memory 142: Unchanged;        Head address managing memory 143:                    Head address of destination C=2→4;                        Tail address managing memory 144: Unchanged.            6) Output of packet C2: FIGS. 41A-41E
When outputting the second packet C2 of the destination C, the memory contents are as follows:                Packet buffer 12: Address 4=free;        Free address managing memory 141:                    Data of address 4 is available;                        Address chain managing memory 142: Unchanged;        Head address managing memory 143:                    Head address of destination C=4→7;                        Tail address managing memory 144: Unchanged.        
It is to be noted that for a reference document, there has been proposed a packet exchanging device and method in which an input buffer portion corresponding to an input line transmits the data assembled by forming a block with packets sequentially having a higher priority for the same output path destination; a scheduler performs a competitive arbitration for the data transmitted and an N×N switch portion switches over the connection of the data to the output line based on the competitive arbitration (see e.g. Patent document 1).
Also, there has been proposed an ATM cell multiplexing method and device in which a single cell buffer is used to manage the storage of the cell buffer with pointer values, the cell buffer is accumulated with ATM cells mixed with different quality classes, and reading from the cell buffer per quality class is made based on the pointer values of the cell buffer stored in a class buffer (FIFO) provided per quality class for a pointer buffer (see e.g. Patent document 2).
Furthermore, there has been proposed a switch and switching method in which a controller included in NIU extracts destination information included in the received data to determine a destination line by associating the destination information and transfer information based on a table; then the received data is transferred to a buffer area through a bus and is temporarily stored in the buffer area; then the controller writes in a queue together with a pointer indicating the address of the data in the buffer area to the effect that the data to be transmitted exists in the buffer area; NIU properly checks the status of the queue and reads the data to be transmitted from the buffer area at a suitable timing based on the pointer in the presence of the data and transmits it to the line (see e.g. Patent document 3).    [Patent document 1]
Japanese patent application laid-open No. 2001-298477    [Patent document 2]
Japanese patent application laid-open No. 2000-78139    [Patent document 3]
Japanese patent application laid-open No. 10-327175
As described above, in the LIU card of the prior art packet transmission device as shown in FIG. 21, packets inputted from the physical ports are once saved or accumulated in the packet buffer, and then transmitted under the control of the scheduler in accordance with a priority class of the packets and transmission rates of the output physical ports.
In this case, the scheduler can not perform a rate control in response to a burst output, so that the packet controller is required to have a packet FIFO by physical port. This enables the packet transmission to be monitored in conformity with the actual rate, where at the occurrence of an abnormal transmission rate due to a burst or the like the packet transmission is stopped while notifying the back pressure signal to the scheduler, thereby stopping the scheduling control for the corresponding physical port.
Meanwhile, a device processing a large quantity of data has been recently required as the number of subscriber increases. Therefore, in case a packet FIFO is provided by physical port as described above, it has been disadvantageous that a time delay of data processing due to packets remaining in the packet FIFO, incurring an increased power consumption and heat generation due to increase of a circuit scale because of the free address managing memory and the address chain managing memory being separately used, as well as an increased heat generation due to downsizing.